/* Alloy Analyzer 4 -- Copyright (c) 2006-2009, Felix Chang
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files
 * (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify,
 * merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF
 * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

package edu.mit.csail.sdg.alloy4graph;

import java.util.ArrayList;
import java.util.List;
import java.awt.geom.CubicCurve2D;

/** Mutable; represents a connected path.
 *
 * <p><b>Thread Safety:</b> Can be called only by the AWT event thread.
 */

final class Curve {

    /** starting position and ending position. */
    public double startX, startY, endX, endY;

    /** The list of segments in this curve. */
    public final List<CubicCurve2D.Double> list = new ArrayList<CubicCurve2D.Double>();

    /** Construct a curve starting at the given location. */
    public Curve(double startX, double startY) {
        this.startX=startX; this.endX=startX;
        this.startY=startY; this.endY=startY;
    }

    /** Make a deep copy of this Curve object. */
    public Curve dup() {
        Curve ans = new Curve(startX, startY);
        ans.endX = endX;
        ans.endY = endY;
        for(CubicCurve2D.Double x:list) {
            CubicCurve2D.Double c = new CubicCurve2D.Double();
            c.setCurve(x);
            ans.list.add(c);
        }
        return ans;
    }
    /** Precondition: this.lastX==next.firstX and this.lastY==next.firstY.
     * Note: the resulting Curve will still share the same CubicCurve2D objects as this and that. */
    Curve join(Curve that) {
        Curve ans = new Curve(startX, startY);
        ans.list.addAll(list);
        ans.list.addAll(that.list);
        ans.endX=that.endX;
        ans.endY=that.endY;
        return ans;
    }

    /** Produce a cubic bezier curve representing a straightline segment from (x1,y1) to (x2,y2) */
    private static CubicCurve2D.Double makeline(double x1, double y1, double x2, double y2) {
        return new CubicCurve2D.Double(x1, y1, (x2-x1)*0.3+x1, (y2-y1)*0.3+y1, (x2-x1)*0.6+x1, (y2-y1)*0.6+y1, x2, y2);
    }

    /** Add a straightline segment to (ax,ay) */
    public Curve lineTo(double ax, double ay) {
        list.add(makeline(endX, endY, ax, ay));
        this.endX = ax;
        this.endY = ay;
        return this;
    }

    /** Add a cubic bezier segment to (cx,cy) using (ax,ay) and (bx,by) as the two control points. */
    public Curve cubicTo(double ax, double ay, double bx, double by, double cx, double cy) {
        list.add(new CubicCurve2D.Double(endX, endY, ax, ay, bx, by, cx, cy));
        this.endX = cx;
        this.endY = cy;
        return this;
    }

    /** Returns true if (x1,y1)..(x2,y2) intersects (x,y3)..(x,y4) */
    private static boolean intersects(double x1, double y1, double x2, double y2, double x, double y3, double y4) {
        if (!(y3<y4)) { double tmp=y3; y3=y4; y4=tmp; }
        if (!((x1<=x && x<=x2) || (x2<=x && x<=x1))) return false;
        double m = (y2-y1)/(x2-x1);
        double i = (x-x1)*m + y1;
        if ((y3<=i && i<=y4) || (y4<=i && i<=y3)) return true; else return false;
    }

    void bendUp(double x, double y1, double y2, double gap) {
        for(int i=0; i<list.size(); i++) {
            CubicCurve2D.Double c=list.get(i);
            if (intersects(c.x1, c.y1, c.x2, c.y2, x, y1, y2)) {
                list.set(i, makeline(c.x1, c.y1, x, y1-gap));
                list.add(i+1, makeline(x, y1-gap, c.x2, c.y2));
                return;
            }
        }
    }

    void bendDown(double x, double y1, double y2, double gap) {
        for(int i=0; i<list.size(); i++) {
            CubicCurve2D.Double c=list.get(i);
            if (intersects(c.x1, c.y1, c.x2, c.y2, x, y1, y2)) {
                list.set(i, makeline(c.x1, c.y1, x, y2+gap));
                list.add(i+1, makeline(x, y2+gap, c.x2, c.y2));
                return;
            }
        }
    }

    /** Chop the start of this curve. */
    public void chopStart(double t) {
        int n=list.size();
        t=t*n;
        double di=StrictMath.floor(t);
        int i=(int)di;
        //
        if (i<0) return;
        if (i>=n) list.clear();
        while(i>0 && !list.isEmpty()) { list.remove(0); i--; }
        if (list.isEmpty()) { list.add(new CubicCurve2D.Double(startX=endX, startY=endY, endX,endY, endX,endY, endX,endY)); return; }
        CubicCurve2D.Double tmp=new CubicCurve2D.Double();
        divide(t-di, list.get(0), new CubicCurve2D.Double(), tmp);
        list.get(0).setCurve(tmp);
        startX=tmp.x1;
        startY=tmp.y1;
    }

    /** Chop the end of this curve. */
    public void chopEnd(double t) {
        int n=list.size();
        t=t*n;
        double di=StrictMath.floor(t);
        int i=(int)di;
        //
        if (i<0) list.clear();
        if (i>=n) return;
        while(i+1<list.size()) list.remove(i+1);
        if (list.isEmpty()) { endX=startX; endY=startY; list.add(new CubicCurve2D.Double(endX,endY, endX,endY, endX,endY, endX,endY)); return; }
        CubicCurve2D.Double tmp=new CubicCurve2D.Double();
        divide(t-di, list.get(i), tmp, new CubicCurve2D.Double());
        list.get(i).setCurve(tmp);
        endX=tmp.x2;
        endY=tmp.y2;
    }

    /** Returns the x position at the given y position, or defaultValue if the line doesn't pass thru the given y position.
     * <p> Precondition: the curve is monotonic in the vertical direction.
     */
    public double getXatY(double y, double startT, double endT, double defaultValue) {
        double a=startT, b=endT, ay=getY(a), by=getY(b);
        if (ay>by) { double tmp=ay; ay=by; by=tmp; a=endT; b=startT; }
        if (!(ay<=y && y<=by)) return defaultValue;
        while(StrictMath.abs(a-b)>0.001D) {
            double t=(a+b)/2, ty=getY(t);
            if (ty==y) {a=t;break;} else if (ty<y) {a=t;} else {b=t;}
        }
        return getX(a);
    }

    /** Returns the x position at the given point 0 <= t <= 1 */
    public double getX(double t) {
        int n=list.size();
        t=t*n;
        double di=StrictMath.floor(t);
        int i=(int)di;
        if (i<0) return startX; else if (i>=n) return endX; else return getX(list.get(i), t-di);
    }

    /** Returns the y position at the given point 0 <= t <= 1 */
    public double getY(double t) {
        int n=list.size();
        t=t*n;
        double di=StrictMath.floor(t);
        int i=(int)di;
        if (i<0) return startY; else if (i>=n) return endY; else return getY(list.get(i), t-di);
    }

    /** Returns the x position of the given segment at the given point 0 <= t <= 1 */
    private double getX(CubicCurve2D.Double curve, double t) {
        double px=(curve.ctrlx1-curve.x1)*t+curve.x1, qx=(curve.ctrlx2-curve.ctrlx1)*t+curve.ctrlx1, rx=(curve.x2-curve.ctrlx2)*t+curve.ctrlx2;
        double sx=(qx-px)*t+px, tx=(rx-qx)*t+qx;
        return (tx-sx)*t+sx;
    }

    /** Returns the y position of the given segment at the given point 0 <= t <= 1 */
    private double getY(CubicCurve2D.Double curve, double t) {
        double py=(curve.ctrly1-curve.y1)*t+curve.y1, qy=(curve.ctrly2-curve.ctrly1)*t+curve.ctrly1, ry=(curve.y2-curve.ctrly2)*t+curve.ctrly2;
        double sy=(qy-py)*t+py, ty=(ry-qy)*t+qy;
        return (ty-sy)*t+sy;
    }

    /** Given 0<=t<=1 and an existing curve, divide it into two chunks and store the two chunks into "first" and "second" */
    public static void divide(double t, CubicCurve2D.Double curve, CubicCurve2D.Double first, CubicCurve2D.Double second) {
        // This algorithm uses de Casteljau's algorithm for chopping one bezier curve into two bezier curves
        first.x1 = curve.x1;
        second.x2 = curve.x2;
        first.ctrlx1 = (1-t)*curve.x1 + t*curve.ctrlx1;
        double x = (1-t)*curve.ctrlx1 + t*curve.ctrlx2;
        second.ctrlx2 = (1-t)*curve.ctrlx2 + t*curve.x2;
        first.ctrlx2 = (1-t)*first.ctrlx1 + t*x;
        second.ctrlx1 = (1-t)*x + t*second.ctrlx2;
        second.x1 = first.x2 = (1-t)*first.ctrlx2 + t*second.ctrlx1;
        // now that we've computed the x coordinates, we now compute the y coordinates
        first.y1 = curve.y1;
        second.y2 = curve.y2;
        first.ctrly1 = (1-t)*curve.y1 + t*curve.ctrly1;
        double y = (1-t)*curve.ctrly1 + t*curve.ctrly2;
        second.ctrly2 = (1-t)*curve.ctrly2 + t*curve.y2;
        first.ctrly2 = (1-t)*first.ctrly1 + t*y;
        second.ctrly1 = (1-t)*y + t*second.ctrly2;
        second.y1 = first.y2 = (1-t)*first.ctrly2 + t*second.ctrly1;
    }
}
